package com.chocho.queue;

public class ArrayLoopQueueDemo {
    public static void main(String[] args) {
        try {
            //创建一个队列
            ArrayLoopQueue queue = new ArrayLoopQueue(3);
//            System.out.println("初始化队列内容");
//            queue.showQueue();

            //输入数据
            queue.addQueue(10);
            queue.addQueue(20);
            queue.addQueue(30);
            //队满插入数据
            queue.addQueue(40);
            queue.showQueue();

            //获取队头数据
            System.out.printf("\n查看队头数据:%d", queue.headQueue());
            System.out.printf("\n获取队头数据:%d", queue.getQueue());
            System.out.printf("\n查看队头数据:%d", queue.headQueue());

        }catch (Exception e){
            e.printStackTrace();
        }
    }
}

/**
 * 关键点：
 * 1.队头在数组地址低位，队尾在数据地址高位
 * 2.队头始终在队头数据，队尾始终在队尾数据的后一个位置，即[front,rear)为队列范围；
 * 因此，front初始化为0，rear初始化为0，才能代表队列为空
 * 3.环形队列，即rear和front在0,1,2,...,maxSize-1递增循环，(rear+1) % maxSize或(front+1) % maxSize
 * 4.队满判断，当再添加一个数据就得添加到front的位置时，代表队满，不可添加数据：(rear+1) % maxSize == front
 * 5.队空判断，队列空时，要保证(front,rear]的集合为空，即front==rear
 * 6.队列中有效数据个数：由于采用了取模循环，因此可以理解为将rear移动到一次模长后面再次取模，这样得到的是队尾的位置，
 * 但是考虑到rear可能是没有取模后的情况，因此需要使用%maxSize来兼顾两种情况 (rear + maxSize - front) % maxSize
 *
 * * 队列实现思路核心关于队头队尾含义的定义，即1.和2.后续规则是为了维护1.和2.而产生的
 */
class ArrayLoopQueue{
    private int maxSize; //数组最大容量
    private int front; //队头下标，数据输出端
    private int rear; //队尾下标，数据输入端
    private int[] arr; //队列数据，模拟队列

    /**
     * 创建队列
     */
    public ArrayLoopQueue(int maxSize){
        this.maxSize = maxSize;
        /**
         * 失败思路分析：
         * 环形队列队头不能为-1，rear只会在0,1,...,maxSize-1中循环，而front初始为-1，则不能正确判满；
         * 若将fornt初始化为0，rear初始化为-1，则无法插入任何数据，需要保证rear >= front
         * 若将fornt初始化为0，rear初始化为0，则数据从1开始插入，即容量为3的队列实际只能容纳2个数据，因此
         * maxSize+1，相当于队列整体后移一位，但是这样实际上会存储maxSize+1个元素，因为下标会从0开始循环
         *
         * 改变思路，重新定义front和rear的含义
         */
        this.front = 0;
        this.rear = 0; //队尾默认在-1位置，-1指向队尾数据
        this.arr = new int[this.maxSize]; //初始化队列
    }

    /**
     * 判断队满
     */
    public boolean isFull(){
        return (this.rear + 1) % this.maxSize == this.front;
    }

    /**
     * 判断队空
     */
    public boolean isEmpty(){
        return this.rear == this.front;
    }

    /**
     * 向队列添加数据
     * @param data
     */
    public void addQueue(int data){
        //判断队满
        if(isFull()){
            System.out.println("队列满，不能添加数据");
            return;
        }
        arr[rear] = data;
        rear = (rear + 1) % maxSize;
    }

    /**
     * 获取队头数据
     * @return
     */
    public int getQueue() throws Exception {
        //判空
        if(isEmpty()){
            throw new Exception("队列为空，不能获取数据");
        }
        int value = arr[front];
        front = (front + 1) % maxSize;
        return value;
    }

    /**
     * 显示队头数据
     * @return
     */
    public int headQueue() throws Exception {
        //判空
        if(isEmpty()){
            throw new Exception("队列为空，不能获取数据");
        }
        return arr[front];
    }

    /**
     * 队列包含元素个数
     * @return
     */
    public int size(){
        return (this.rear + this.maxSize - this.front) % this.maxSize;
    }

    /**
     * 显示队列数据
     */
    public void showQueue() throws Exception {
        if(isEmpty()){
            throw new Exception("队列为空，不能获取数据");
        }

        System.out.print("[");
        for (int i = front; i <= front + size(); i++){
            System.out.printf("[%d]=%d\t", i, arr[i]);
        }
        System.out.print("]");
    }
}
